// https://www.lintcode.com/problem/image-smoother/

public class Solution {
    /**
     * @param M: a 2D integer matrix
     * @return: a 2D integer matrix
     */
    public int[][] imageSmoother(int[][] M) {
        // Write your code here
        int rows = M.length, cols = M[0].length;
        int[][] ret = new int[rows][cols];
        for (int r = 0; r < rows; ++r) {
            for (int c = 0; c < cols; ++c) {
                ret[r][c] = smoother(M, r, c);
            }
        }
        return ret;
    }
    
    protected int smoother(int[][] M, int r, int c) {
        int rows = M.length, cols = M[0].length;
        int val = M[r][c], count = 1;
        if (((r - 1) >= 0) && ((c - 1) >= 0)) { // upper-left
            val += M[r - 1][c - 1];
            ++count;
        }
        if ((r - 1) >= 0) { // upper
            val += M[r - 1][c];
            ++count;
        }
        if (((r - 1) >= 0) && ((c + 1) < cols)) { // upper-right
            val += M[r - 1][c + 1];
            ++count;
        }
        if ((c - 1) >= 0) { // left
            val += M[r][c - 1];
            ++count;
        }
        if ((c + 1) < cols) { // right
            val += M[r][c + 1];
            ++count;
        }
        if (((r + 1) < rows) && ((c - 1) >= 0)) { // down-left
            val += M[r + 1][c - 1];
            ++count;
        }
        if ((r + 1) < rows) { // down
            val += M[r + 1][c];
            ++count;
        }
        if (((r + 1) < rows) && ((c + 1) < cols)) { // down-right
            val += M[r + 1][c + 1];
            ++count;
        }
        return val / count;
    }
}